﻿/*
* File: construct subgroup function3
* Author: Dongcheng Li
* Date: 20191015
* Purpose: construct subgroup of Zn*
* https://w.ketangpai.com/pages/homework/homework-detail.html
*/

#include <iostream>
#include<stack>
#include<algorithm>
using namespace std;
/*
*Input: an integer p
* Output : return the result of subgroup.
* Purpose : construct subgroup of Zn*
* Method : By using the  Eurler Theorem.
*/
int GCD(int integer_a, int integer_b)//return the result of GCD.
{
	int container;
	while (integer_b != 0)
	{
		container = integer_a;
		integer_a = integer_b;
		integer_b = container % integer_b;
	}
	return integer_a;
}

int Eurler(int integer_n) {//return the result of Eurler.
	int counter;
	int counter_2 = 0;
	for (counter = 1; counter < integer_n; counter++)
	{
		if (GCD(integer_n, counter) == 1)
		{

			counter_2++;
		}
	}
	return counter_2;
}
int construct_Subgroup3(int p) {
	int g;
	int i;//Traversing counter
	int j;//Traversing counter2
	int k;//Repeat counter
	int flag;//Is it redundant
	int order;
	int n;
	n = 2;
	int* a = new int[n];
	j = 0;
	cout << "choose two from: ";
	for (i = 0; i < p; i++)
	{
		if (GCD(p, i) == 1)
		{
			cout << i << " ";
		}
	}
	cin >> a[0] >> a[1];
	for (i = 0; i < n; i++) {
		for (j = i + 1; j < n; j++)
		{
			flag = 0;
			for (k = 0; k < n; k++)
			{
				if ((a[i] * a[j]) % p == a[k])
				{
					flag = 1;
				}
			}
			if (flag == 1) {
				continue;
			}
			else {
				a[n] = (a[i] * a[j]) % p;//Do not repeat elements at the end of the array
				n++;//Array length+1
			}

		}
	}
	//cout <<  "S set: ";
	//for (i = 0; i < n; i++) { cout << a[i] << " "; }
	//cout << "\n";
	return n;
}
int main()
{
	int prime_N;
	cout << "N:" << endl;
	cin >> prime_N;

	cout << "order:" << construct_Subgroup3(prime_N);
}
/*int construct_Subgroup3(int p) {//n是欧拉函数的结果
	int g;
	int i, j,k,flag;
	int order;
	int n;
	n = Eurler(p);
	int*a=new int [n];

	j = 0;
	for (i = 0; i < p; i++)
	{
		if (GCD(p, i) == 1)
		{

			a[j]=i;
			j++;
		}
	}
	for (i = 0; i < n;i++) {
		for (j=i+1; j <n ; j++)
		{
			flag = 0;
			for (k = 0; k < n; k++)
			{
				if((a[i] * a[j]) % p==a[k])
				{
					 flag=1;
				}
			}
			if (flag == 1) {
				continue;
			}
			else {
				a[n + 1] = (a[i] * a[j]) % p;//不重复元素放入数组末尾
				n++;//数组长度+1
			}

		}
	}

	return n;
}*/